/*
 * Title: 丑数（Ugly Numbers）
 * Author: Yuanshun L
 * Created : 10-otc-2021
 * Question Description: 丑数是是指不能被2,3,4之外的其他素数整除的数
 */

#include<iostream>
#include<queue>
#include<vector>
#include<set>
using namespace std;

#define COUNT 1500
#define TIMES_NUM 3
typedef long long LL;
// 优先队列，数值小的优先级高
priority_queue<LL,vector<LL>,greater<LL> > pq;
set<LL> st;
int times[TIMES_NUM] = {2,3,5};


int main(){
     int rnd=0;
     LL temp,temp2;
     // 初始化队列
     pq.push(1);

     while(rnd<COUNT){
         temp = pq.top();
         rnd++;
         if(rnd==COUNT){
             cout<<"The "<<COUNT<<"' ugly number is "<<temp<<endl;
             break;
         }
         st.erase(temp); // 从集合中擦除
         pq.pop(); // 弹出

         // 把temp后面三个丑数入队
         for(int i=0;i<TIMES_NUM;i++){
             // 没有在队中则入队
             temp2 = times[i]*temp;
             if(!st.count(temp2)){
                 st.insert(temp2);
                 pq.push(temp2);
             }
         }
     }

    return 0;
}